package com.azure.code.graph.unionFind;

/**
 * UF 路径压缩优化 将 扁平化树 将算法复杂度降为O(1)
 *
 * 从UF->UFBalance->UFPathCompress优化逻辑：
 * 1、用parent数组记录每个节点的父节点，相当于指向父节点的指针，所有parent数组内实际存储一个森林(若干颗多叉树)
 * 2、用size数组记录每颗树的重量，目的是让union后树依然拥有平衡性，保证各个API时间复杂度为O(logN)，而不会退化
 *    成链表影响操作效率 UFBalance
 * 3、在find函数中进行路径压缩，保证任意树的高度保持在常数，使得各个API时间复杂为O(1)。使用路径压缩之后，可以不使用
 *    size数组的平衡优化 UFPathCompress
 *
 */
public class UFPathCompress {
    private int count;
    private final int[] parent;

    public UFPathCompress(int n) {
        this.count = n;
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public  void  union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ) {
            return;
        }
        // 合并两颗树
        parent[rootP] = rootQ;
        count--;
    }

    public boolean connected(int p ,int q){
        return find(p)==find(q);
    }

    /**
     *  路径压缩优化
     */
    private int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}
